home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / toolbox.me < prev    next >
Text File  |  1992-09-25  |  47KB  |  1,420 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .\" .po 3.0c    \" page offset (left margin)
  380. .\" .ll 15.9c    \" line length
  381. .\" .lt 15.9c    \" title length
  382. .hc ~
  383. .ds ], , 
  384. .EQ
  385. gsize 12
  386. delim $$
  387. .EN
  388. .b " "
  389. .sp 1c
  390. .ta 9c
  391. .ft R
  392. .sz 12
  393. \l'17.1c'
  394. .nf
  395.  
  396.  
  397.     A Tool Box for
  398.     Compiler Construction
  399.  
  400.     J. Grosch
  401.     H. Emmelmann
  402.  
  403. \l'17.1c'
  404. .sp 12.5c
  405. \l'17.1c'
  406. .ft H
  407. .nf
  408.     GESELLSCHAFT F\*UR MATHEMATIK
  409.     UND DATENVERARBEITUNG MBH
  410.  
  411.     FORSCHUNGSSTELLE F\*UR
  412.     PROGRAMMSTRUKTUREN
  413.     AN DER UNIVERSIT\*AT KARLSRUHE
  414. .r
  415. \l'17.1c'
  416. .bp
  417. .oh '''%'
  418. .eh '''%'
  419. .ce 99
  420. .sz 20
  421. .b " "
  422. .sp 2
  423. Project
  424. .sp
  425. .b "Compiler Generation"
  426. .sp
  427. .sz 12
  428. \l'15c'
  429. .sp
  430. .sz 16
  431. .b "A Tool Box for Compiler Construction"
  432. .sp 2
  433. Josef Grosch
  434. Helmut Emmelmann
  435. .sp 2
  436. .sz 14
  437. Jan. 21, 1990
  438. .sp
  439. .sz 12
  440. \l'15c'
  441. .sp 2
  442. Report No. 20
  443. .sp 2
  444. Copyright \(co 1990 GMD
  445. .sp 2
  446. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  447. Forschungsstelle an der Universit\*at Karlsruhe
  448. Vincenz-Prie\*snitz-Str. 1
  449. D-7500 Karlsruhe
  450. .ce 0
  451. .fi
  452. .bp 1
  453. .b " "
  454. .sp 3
  455. .ce 99
  456. .sz +2
  457. .b "A Tool Box for Compiler Construction"
  458. .sz -2
  459. .sp 2
  460. J. Grosch, H. Emmelmann
  461. GMD Forschungsstelle an der Universit\*at Karlsruhe
  462. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  463. .\" Tel: +721-6622-26
  464. E-Mail: grosch@karlsruhe.gmd.de, emmel@karlsruhe.gmd.de
  465. .ce 0
  466. .sp 3
  467. .uh Abstract
  468. .pp
  469. .\" This paper presents a rather complete set of tools supporting the construction of all phases of a
  470. .\" compiler. The tools are very powerful and flexible in order to be useful for wide ranges of
  471. .\" compiler designs and programming languages. The modules generated by the tools allow the
  472. .\" construction of production quality compilers. Currently modules in the target languages C and
  473. .\" Modula-2 can be generated. First realistic applications demonstrate the excellent performance
  474. .\" of the tools.
  475. .\" We designed and implemented a rather complete set of tools to support the construction of high
  476. .\" quality compilers. The tool box currently contains the following tools
  477. .\" covering most phases of a compiler:
  478. This paper presents a set of tools supporting 
  479. the construction of nearly every compiler phase.
  480. Design goals of this tool box have been practical usability,
  481. significantly reduced effort for compiler construction,
  482. and high quality of the generated compilers.
  483. Especially efficiency should be competitive to hand crafting.
  484. .pp
  485. Currently modules in the target languages C and Modula-2 can be generated.
  486. First realistic applications demonstrate the excellent performance of the tools and
  487. show that the tools allow the construction of production quality compilers.
  488. .sh 1 Introduction
  489. .pp
  490. Within this paper we present a compiler generation tool box.
  491. It contains tools for nearly every compiler phase. We believe the 
  492. tools are applicable for realistic compiler projects.
  493. .pp
  494. The tools generally accept as input a specification written in 
  495. a language specific to the tool and produce modules in
  496. a target language (C or Modula-2). Therefore a tool can be 
  497. seen as a generic solution of a compilation subproblem,
  498. which is instantiated by the specification.
  499. .pp
  500. Using tools instead of hand crafting a compiler has several advantages:
  501. The effort necessary to build a compiler is substantially 
  502. reduced. Instead of writing a program a much shorter specification
  503. has to be developed. The tools can perform many consistency checks 
  504. on the specifications. Writing automatically checked specifications
  505. drastically reduces the amount of possible errors and hence 
  506. increases the reliability of the resulting compiler.
  507. .pp
  508. The tool box consists of the following tools:
  509. .(b
  510. .ta 2c
  511. Rex    scanner generator
  512. Lalr    LALR(1) parser generator
  513. Ell    LL(1) parser generator
  514. Ast    generator for abstract syntax trees
  515. Ag    attribute evaluator generator
  516. Estra    transformation of attributed syntax trees
  517. Beg    back end generator
  518. Reuse    library of reusable modules
  519. .)b
  520. .pp
  521. All the tools were originally programmed in Modula-2 and run under UNIX. Using the Modula-2
  522. to C translator called
  523. .i Mtc
  524. \*([[Mar90\*(]] (see section 6.1), the sources also exist in C. Currently most
  525. of the tools generate modules in the target languages C and Modula-2.
  526. .\" Using the tool box to construct compilers has several advantages in comparison to an
  527. .\" implementation by hand. A large percentage of programming is replaced by
  528. .\" writing specifications. The
  529. .\" tools drastically reduce the construction effort for compilers. The use of specifications
  530. .\" enables the tools to perform consistency checks thus avoiding many errors. The automatic
  531. .\" generation of program modules increases their reliability. The efficiency of the generated
  532. .\" modules is comparable to hand-written implementations.
  533. .pp
  534. The next two sections present the design goals and the common features of the tools.
  535. Section 4 describes the compiler model we prefer.
  536. In section 5 all the tools are sketched briefly.
  537. Section 6 reports about the experiences of two realistic applications of the tools.
  538. Section 7 gives a summary and describes future work.
  539. .sh 1 "Design Goals"
  540. .pp
  541. The major design goals of the tool box were:
  542. .ip -
  543. practical usability for realistic languages
  544. .ip -
  545. automatic generation of production quality compilers
  546. .ip -
  547. substantial increase in compiler construction productivity and compiler reliability
  548. .ip -
  549. quality of the resulting compiler competitive to hand crafting 
  550. .pp
  551. By defining these goals we wanted to produce a tool box which
  552. will be used in practical compiler construction work.
  553. Therefore we considered competitiveness to hand crafting important,
  554. because we feel that tools promising a high productivity and reliability
  555. but which produce compilers whose code quality 
  556. or efficiency is lower than hand crafted compilers, will hardly be used.
  557. .sh 1 "Common Implementation Decisions"
  558. .pp
  559. Our design goals lead to several design decisions common to all of our tools. 
  560. Nearly every tool needs a programming language in which the user can specify certain
  561. actions, conditions, or calculations. That is obviously 
  562. true for attribute grammars, but also the back end
  563. generator needs to evaluate several attributes and 
  564. conditions. Even the parser generators need such a language for the
  565. specification of semantic actions.
  566. .pp
  567. We decided to select the target language (namely C or Modula-2).
  568. Specifications therefore may contain pieces of target language code.
  569. Besides some pattern replacement the text is copied unchanged to the generated modules.
  570. The disadvantage of that method is that the target language
  571. code can not be checked completely by the tool. 
  572. For example the attribute grammar tool can not check if 
  573. attribute evaluations do not have side-effects.
  574. On the other hand it gives a great deal of flexibility,
  575. as the whole power of the target language is available.
  576. It also drastically increases the practical usability,
  577. as interfacing to other components (perhaps hand-written ones) is easily possible.
  578. It finally keeps the tools and the specification languages
  579. simple. The user is not forced to learn a new language to express conditions or actions.
  580. .pp
  581. Our experience with prior tools is that during realistic compiler design 
  582. a lot of small special problems occur, which the tool can not handle. 
  583. Therefore loopholes, possibilities how the user of the tools can
  584. easily plug in hand-written parts, are necessary. 
  585. Loopholes also allow to keep tools simple, as one is not forced
  586. to provide a solution for every special case, immediately. 
  587. It is possible to use the loophole until a really good solution
  588. is found to be build in a tool.
  589. .pp
  590. The tools are largely independent of each other. This is 
  591. achieved by the property that none of the generated modules has a fixed kind of output.
  592. Instead this output is specified using statements from the target language and thus can be
  593. chosen arbitrarily.
  594. .\" This way, it is also easily possible to add hand-written parts to the generated ones.
  595. The independence of the tools allows for a large degree of freedom in the
  596. compiler design. An exception are the tools
  597. .i Ag
  598. and
  599. .i Estra
  600. which operate on syntax trees specified using
  601. .i Ast .
  602. Therefore they depend on
  603. .i Ast
  604. and all three tools require the compiler to use an attributed abstract syntax tree.
  605. .\" The main design goal for the tools was to allow the largely automatic generation of
  606. .\" production quality compilers for real languages such as Modula-2, C, or Ada. All the
  607. .\" following goals are more or less consequences of this main goal. The tools set should be
  608. .\" complete and support all phases of a compiler. Each tool should be simple and easy to use by
  609. .\" concentrating on the specification of the underlying concepts. Yet, every tool has to be
  610. .\" powerful enough to be able to handle not only toy languages but realistic ones. The tools
  611. .\" should be open and flexible to allow many compiler designs and they should provide loopholes
  612. .\" to cope with the malices of existing language definitions. Last but not least the program
  613. .\" modules generated by the tools should be as efficient as possible primarily in terms of run
  614. .\" time.
  615. .\" .pp
  616. .\" The tools share several common features. They are largely independent of each other. This is
  617. .\" achieved by the property that none of the generated modules has a fixed kind of output.
  618. .sh 1 "Compiler Model"
  619. .(z
  620. .PS
  621. linewid    = linewid * 1.2
  622. boxwid    = boxwid * 1.7
  623. boxht    = boxht * 1.2
  624. circlerad = circlerad * 1.2
  625. bh    = boxht * 1.7
  626. bw    = boxwid * 0.5
  627.  
  628.     right
  629.  
  630. S1:    box wid bw height bh invis
  631. SP:    box wid boxwid * 1.6 "Scanner spec:" "regular expressions"
  632.     arrow
  633. T:    circle "rex"
  634.     arrow
  635. I1:    box "Scanner"
  636.  
  637. S2:    box at S1 - (0, bh) wid bw height bh invis
  638. P:    box wid boxwid * 1.6 "Parser spec:" "concrete syntax (grammar)" "mapping: concrete \(-> abstract"
  639.     arrow
  640.     circle "lalr" "ell"
  641.     arrow
  642. I2:    box "Parser"
  643.  
  644. S3:    box at S2 - (0, bh) wid bw height bh invis
  645.     box wid boxwid * 1.6 "Tree spec:" "abstract syntax" "(grammar)"
  646.     arrow
  647.     circle "ast"
  648.     arrow
  649. I3:    box "Tree"
  650.  
  651. S4:    box at S3 - (0, bh) wid bw height bh invis
  652.     box wid boxwid * 1.6 "Semantics spec:" "attribute grammar"
  653.     arrow
  654.     circle "ag"
  655.     arrow
  656. I4:    box "Semantics"
  657.  
  658. S5:    box at S4 - (0, bh) wid bw height bh invis
  659.     box wid boxwid * 1.6 "Trafo spec:" "mapping:" "abstract \(-> intermediate"
  660.     arrow
  661.     circle "estra"
  662.     arrow
  663. I5:    box "Trafo"
  664.  
  665. S6:    box at S5 - (0, bh) wid bw height bh invis
  666.     box wid boxwid * 1.6 "Intermediate spec:" "intermediate language" "(grammar)"
  667.     arrow
  668.     circle "ast"
  669.     arrow
  670. I6:    box "Intermediate"
  671.  
  672. S7:    box at S6 - (0, bh) wid bw height bh invis
  673.     box wid boxwid * 1.6 "Codegenerator spec:" "mapping:" "intermediate \(-> machine"
  674.     arrow
  675.     circle "beg"
  676.     arrow
  677. I7:    box "Codegenerator"
  678.  
  679.     box invis "Specification" at SP + (0, bh)
  680.     box invis "Tool" at T + (0, bh)
  681.     box invis "Compiler" "Module" at I1 + (0, bh)
  682.  
  683.     line from I1.n up boxht * 0.9 <-
  684.     arrow from I1.s to I2.n
  685.     arrow from I2.s to I3.n
  686.     arrow from I3.s to I4.n <->
  687.     arc from I3.se to I5.ne at I4 -> cw
  688.     arrow from I5.s to I6.n
  689.     arrow from I6.s to I7.n
  690.     arrow from I7.s down boxht * 0.9
  691. .PE
  692. .sp 0.5
  693. .ce
  694. Fig. 1: Compiler Model
  695. .)z
  696. .pp
  697. Although the tools do not directly enforce any specific compiler model, we want to present
  698. the model we prefer and which we believe is supported best by the tools. We still consider
  699. semantic analysis to be the hard part of a compiler. Therefore we base semantic analysis and
  700. the generation of an intermediate language on the abstract syntax. We explicitly construct
  701. the abstract syntax tree which might be decorated with attributes during semantic analysis.
  702. Besides the abstract syntax, which can be regarded as a first (high-level) intermediate
  703. representation, we prefer to use a second (low-level) intermediate representation as
  704. interface to the code generator. This has advantages for optimizations and for pattern
  705. directed code selection.
  706. .pp
  707. Figure 1 shows our preferred compiler model. In the right column are the main modules
  708. that constitute a compiler. The left column contains the necessary specifications. In
  709. between there are the tools which are controlled by the specifications and which produce the
  710. modules. The arrows represent the data flow in part during generation time and in part during
  711. run time.
  712. .pp
  713. In principle the compiler model works as follows: a scanner and a parser read the source,
  714. check the concrete syntax, and construct an abstract syntax tree. They may perform several
  715. normalizations, simplifications, or transformations in order to keep the abstract syntax
  716. relatively simple. Semantic analysis is performed on the abstract syntax tree. Optionally
  717. attributes for code generation may be computed. Afterwards the abstract syntax tree is
  718. transformed into an intermediate representation. The latter is the input of the code generator
  719. which finally produces the machine code.
  720. .sh 1 "The Tools"
  721. .pp
  722. The following sections briefly sketch the tools that make up the tool box. We only describe the
  723. features of the tools - for details, for the specification techniques, or for examples there
  724. exist separate documents.
  725. .sh 2 Rex
  726. .pp
  727. The scanner generator \fIRex\fP has been developed with the aim to combine
  728. the powerful specification method of regular expressions with the generation
  729. of highly efficient scanners
  730. \*([[Gro87b\*(],Gro88\*(],Gro89a\*(]].
  731. The name \fIRex\fP stands for
  732. .i "regular expression tool,"
  733. reflecting the specification method.
  734. .pp
  735. A scanner specification consists in principle of a set of regular
  736. expressions each associated with a semantic action. Whenever a string
  737. constructed according to a regular expression is recognized in the input of
  738. the scanner its semantic action which is a sequence of arbitrary statements
  739. written in the target language is executed. To be able to recognize tokens
  740. depending on their context, \fIRex\fP provides start states to handle left context
  741. and the right context can be specified by an additional regular expression.
  742. If several regular expressions match the input characters, the
  743. longest match is preferred. If there are still several possibilities, the
  744. regular expression given first in the specification is chosen.
  745. .pp
  746. \fIRex\fP generated scanners automatically provide the line and column position of
  747. each token. For languages like Pascal and Ada where the case of letters is
  748. insignificant tokens can be normalized to lower or upper case. There are
  749. predefined rules to skip white space like blanks, tabs, or newlines
  750. and there is a mechanism to handle include files.
  751. .\" pp
  752. The generated scanners are table-driven deterministic finite automatons. The
  753. tables are compressed using the so-called comb-vector technique
  754. \*([[ASU86\*(]].
  755. .\" Whereas the generator \fIRex\fP is implemented in Modula-2
  756. .\" it can generate scanners in the languages C and Modula-2. Currently \fIRex\fP is
  757. .\" available for PCS Cadmus/UNIX and SUN/UNIX workstations.
  758. .pp
  759. The most outstanding feature of \fIRex\fP is its speed. The generated scanners
  760. process nearly 200,000 lines per minute without hashing of identifiers and
  761. up to 150,000 lines per minute if hashing is applied.
  762. (Keywords do not require hashing if they are recognized directly by the generated automaton.)
  763. This is 4 times the
  764. speed of \fILex\fP\*([<\*([[Les75\*(]]\*(>] generated scanners. In typical cases \fIRex\fP generated
  765. scanners are 4 times smaller then \fILex\fP generated ones. Usually
  766. \fIRex\fP takes only 1/10 of the time of \fILex\fP to generate a scanner.
  767. .\" All figures have been measured on a MC 68020 processor.
  768. .sh 2 Lalr
  769. .pp
  770. The parser generator \fILalr\fP has been developed with the aim to combine a
  771. powerful specification technique for context-free languages with the
  772. generation of highly efficient parsers\*([<\*([[Gro88\*(],GrV88\*(]]\*(>].
  773. As it processes the class of LALR(1) grammars we chose the name \fILalr\fP to
  774. express the power of the specification technique.
  775. .pp
  776. The grammars may be written using EBNF constructs. Each grammar rule
  777. may be associated with a semantic action consisting of arbitrary statements
  778. written in the target language. Whenever a grammar rule is recognized by the
  779. generated parser the associated semantic action is executed. A mechanism for
  780. S-attribution (only synthesized attributes) is provided to allow
  781. communication between the semantic actions.
  782. .pp
  783. In case of LR-conflicts a derivation tree is printed to ease the location of the
  784. problem. The conflict can be resolved by specifying precedence and
  785. associativity for terminals and rules. Syntactic errors are handled fully
  786. automatically by the generated parsers including error reporting, recovery,
  787. and repair.
  788. .\" The mentioned features are discussed in more detail in the following chapters.
  789. .\" pp
  790. The generated parsers are table-driven. Like in the case of \fIRex\fP,
  791. comb-vector technique is used to compress the parse tables.
  792. .\" The generator \fILalr\fP is implemented in the language Modula-2. Parsers
  793. .\" can be generated in the languages C and Modula-2.
  794. The generator uses the algorithm described by
  795. \*([[DeP82\*(]] to compute the look-ahead sets.
  796. .\" although the algorithm published by .[ives.] promises to perform better.
  797. .\" Currently \fILalr\fP is available for PCS-Cadmus/UNIX and SUN/UNIX workstations.
  798. .pp
  799. Parsers generated by \fILalr\fP are two to three times faster than \fIYacc\fP
  800. \*([[Joh75\*(]] generated
  801. ones. They reach a speed of 580,000 lines per minute on a MC 68020 processor
  802. excluding the time for scanning. The size of the parsers is only slightly
  803. increased in comparison to \fIYacc\fP, because there
  804. is a small price to be paid for the speed.
  805. .sh 2 Ell
  806. .pp
  807. The parser generator \fIEll\fP processes LL(1) grammars which may contain EBNF
  808. constructs and semantic actions. It generates recursive descent parsers
  809. \*([[Gro88\*(],GrV88\*(],Gro89b\*(]].
  810. A mechanism for L-attribution (inherited and synthesized attributes
  811. evaluable during one preorder traversal) is provided. Like \fILalr\fP, syntax
  812. errors are handled fully automatic including error reporting from a prototype
  813. error module, error recovery, and error repair.
  814. .\" The generator \fIEll\fP is implemented in Modula-2 and can generate parsers in C and Modula-2.
  815. Those satisfied with the restricted power of LL(1) grammars may profit from the
  816. high speed of the generated parsers which lies around 900,000 lines per minute.
  817. .\" For a detailed comparison see Figure 12.
  818. .sh 2 Ast
  819. .pp
  820. .i Ast
  821. is a generator for \fIa\fPbstract \fIs\fPyntax \fIt\fPrees
  822. \*([[Gro91a\*(],Gro91b\*(]].
  823. It generates program modules or abstract data types
  824. to handle attributed trees. Besides trees attributed graphs can be handled as well. The nodes
  825. of these data structures may be associated with arbitrary many attributes of arbitrary type.
  826. The specifications for this tool are based on extended tree grammars.
  827. They can be regarded as a common notation for concrete and abstract syntax as well as for
  828. attributed trees and graphs. An extension mechanism provides single inheritance. Internally
  829. the trees are stored as linked records.
  830. .i Ast
  831. can be requested to generate many operations for trees:
  832. node constructors combine aggregate notation and storage management. Reader and writer
  833. procedures transfer graphs from/to files in ASCII or binary format. The order of subtrees
  834. in a list can be reversed. Procedures for commonly used traversal strategies like top down
  835. (depth first) or bottom up (reverse depth first) are provided. An interactive graph browser
  836. allows the inspection of graphs in a readable way and thus supports debugging.
  837. .sh 2 Ag
  838. .pp
  839. .i Ag
  840. is an attribute evaluator generator\*([<\*([[Gro89d\*(],Gro90\*(]]\*(>].
  841. It processes ordered attribute grammars (OAGs)\*([<\*([[Kas80\*(]]\*(>]
  842. as well as higher order attribute grammars (HAGs)\*([<\*([[VSK89\*(]]\*(>].
  843. It is based on the abstract syntax or to be more specific on tree modules generated by
  844. .i Ast .
  845. Therefore the tree structure is fully known.
  846. The terminals and nonterminals may have arbitrary many attributes
  847. which can have any target language type.
  848. This includes tree-valued attributes.
  849. .\" - differentiates input and output attributes
  850. .i Ag
  851. allows attributes local to rules and offers an extension mechanism which provides (single)
  852. inheritance for attributes and for attribute computations.
  853. It also allows the elimination of chain rules.
  854. .\" The attributes are denoted by unique selector names instead of nonterminal names with subscripts.
  855. The attribute computations are expressed in the target language and should be written
  856. in a functional style.
  857. It is possible to call external functions of separately compiled modules.
  858. Non-functional statements and side-effects are possible but require careful consideration.
  859. The syntax of the specification language is designed to support compact, modular,
  860. and readable documents.
  861. An attribute grammar can consist of several modules
  862. where the context-free grammar is specified only once.
  863. .\" - checks an AG for completeness of the attribute computations
  864. .\" - checks for unused attributes
  865. .\" - checks an AG for the classes SNC, DNC, OAG, LAG, and SAG
  866. There are shorthand notations for copy rules and threaded attributes which allow the user to
  867. omit many trivial attribute computations.
  868. The generated evaluators are very efficient because they are directly coded using
  869. recursive procedures.
  870. Attribute storage is optimized by implementing attributes as local variables and procedure
  871. parameters whenever their lifetime is contained within one visit.
  872. .\" - generates efficient evaluators
  873. .\" - generates evaluators in Modula-2 (or C)
  874. .sh 2 Estra
  875. .pp
  876. .i Estra
  877. is a generator for \fIe\fPfficient \fIs\fPyntax \fItr\fPee \fItra\fPnsformers
  878. \*([[Vie89\*(]]. The generated
  879. transformation modules take an attributed tree as input and map it to an arbitrary output.
  880. The output can be a new tree, a linear code such as e. g. P-Code, source code like e. g.
  881. Pascal, or a sequence of procedure calls. In any case the input tree remains unchanged in
  882. order to avoid to reevaluate the attributes for reasons of consistency. However, subtrees of
  883. the input tree may be reused to construct an output tree. The intended application areas for
  884. the transformations are the generation of intermediate representations out of abstract syntax
  885. trees and optimizers operating on internal tree representations of any level.
  886. .i Estra
  887. cooperates with
  888. .i Ast :
  889. the input trees are constructed by modules generated with the latter tool.
  890. .pp
  891. The specification of a transformer is rule based. A rule consists of a pattern describing a
  892. tree fragment and an action. Actions are composed of target language statements. It is
  893. possible to specify several transformations. The subtrees of a pattern can be transformed in
  894. any order. They can be transformed several times by the same or by different transformations.
  895. The actions have read access to the attributes of the input tree. Additional synthesized
  896. and inherited attributes may be evaluated during the transformation. The application of rules
  897. can be restricted by conditions. Ambiguities may be resolved using costs.
  898. .pp
  899. Two
  900. implementations of the pattern-matcher can be selected: a directly coded dynamic programming
  901. algorithm or a table-driven tree pattern-matcher. In both cases the transformation has two
  902. phases. While the first one determines the patterns that match with minimal costs the second
  903. one executes the associated actions.
  904. .sh 2 Beg
  905. .pp
  906. .i Beg
  907. (a \fIb\fPack \fIe\fPnd \fIg\fPenerator) produces code selectors and register 
  908. allocators\*([<\*([[Emm89a\*(],Emm89b\*(]]\*(>].
  909. Code selection is performed using tree pattern matching.
  910. The target instructions are described using rules containing tree patterns.
  911. The resulting code generator accepts a tree oriented intermediate
  912. language. An input tree is translated by covering the tree by the patterns
  913. and afterwards emitting the corresponding instructions.
  914. Rules are annotated with cost values which allows the code 
  915. generator to select a cover of minimal cost, that means the sum
  916. of the costs of all rules in the cover is minimal.
  917. .pp
  918. Therefore the user only describes ambiguously how certain intermediate 
  919. language constructs 
  920. can be translated. He need not to program the algorithm to 
  921. select the best way to translate a specific input tree. 
  922. A good way to develop a code generator description is to first
  923. describe only a subset of the machine's instructions, big enough 
  924. to compile the whole language. This results in a running
  925. compiler, which may produce inefficient code.
  926. Afterwards gradually more and more rules can be added 
  927. which finally leads to a compiler producing good code.
  928. .pp
  929. .i Beg
  930. implements the determination of the minimal cover using a
  931. directly coded version of the dynamic programming algorithm
  932. \*([[Emm89a\*(],ESL89\*(]].
  933. .pp
  934. The generation of register allocators is of specific importance, because
  935. hand crafting is a rather difficult and tedious job and because
  936. errors in the register allocator are sometimes very difficult to find.
  937. Within rules, the characteristics with respect to register allocation
  938. of an instruction can be specified: the allowed registers for 
  939. each operand, the registers changed by side-effects, and 
  940. whether the instruction is a two address instruction or not.
  941. Additionally the register set of the target machine has to be described.
  942. Even the double register problem (e. g. IBM 370) can be handled.
  943. .pp
  944. Two kinds of local register allocators can be requested: the on the fly
  945. register allocator handles simple register sets.
  946. However, it provides satisfying results for many machines and is very efficient.
  947. In some cases the general register allocator is
  948. necessary which performs some kind of look-ahead.
  949. Therefore it requires an extra pass.
  950. .\" .i Beg
  951. .\" is a \fIb\fPack \fIe\fPnd \fIg\fPenerator that produces modules for code selection
  952. .\" and for register allocation\*([<\*([[ESL89\*(]]\*(>].
  953. .\" The code selectors are specified in a strictly declarative style. A specification consists of
  954. .\" a description of the input language and a set of rules. The input language is basically an
  955. .\" attributed tree. However, this tree is not stored in memory, it is transferred by a series of
  956. .\" procedure calls.
  957. .\" .i Beg
  958. .\" generates a procedure for every node type or operator respectively. The parameters of the
  959. .\" procedures describe the sons or operands and the attributes.
  960. .\" .pp
  961. .\" The rules consist of a pattern and an action. Again, the actions are formulated using
  962. .\" statements of the target language. This gives a large degree of freedom  and allows for
  963. .\" example the production of readable assembly code as well as binary machine code. The actions
  964. .\" may also evaluate attributes during code selection. Again, the application of rules can be
  965. .\" restricted by conditions and costs may be used to resolve ambiguities.
  966. .\" Pattern-matching is implemented by a directly coded dynamic programming algorithm.
  967. .\" It works in two phases where the first one determines the applicable and cheapest patterns
  968. .\" and the second one executes the associated actions.
  969. .\" .pp
  970. .\" Two kinds of register allocators can be requested. The on the fly register allocator provides
  971. .\" satisfying results for many simple machines. In some cases, however, the general register
  972. .\" allocator is necessary which performs some kind of look-ahead. It therefore minimizes the
  973. .\" generation of register copy and register spilling operations. While the on the fly register
  974. .\" allocator is integrated with the actions, the general method requires an additional phase.
  975. .sh 2 Reuse
  976. .pp
  977. .i Reuse
  978. is a library of reusable modules oriented towards compiler construction
  979. \*([[Gro87a\*(]]. It contains modules or abstract data types which are needed in
  980. almost every compiler:
  981. .ip -
  982. a dynamic storage handler
  983. .ip -
  984. a module that provides dynamic and flexible arrays
  985. .ip -
  986. a facility to store strings of arbitrary length
  987. .ip -
  988. a module for string handling
  989. .ip -
  990. an identifier table which maps strings to unique integers using hashing
  991. .ip -
  992. modules for commonly used data structures such as sets of integers or binary relations
  993. between integers with no limitation of the domain
  994. .sh 1 "Application Experiences"
  995. .pp
  996. This section reports the experience of applying the tool box for realistic problems.
  997. .sh 2 "Modula to C Translator"
  998. .pp
  999. The largest application for the tool box so far was the generation of a Modula-2 to C
  1000. translator\*([<\*([[Mar90\*(]]\*(>]. The program called
  1001. .i Mtc
  1002. translates Modula-2 programs into readable C code without any restrictions
  1003. (even nested procedures and modules).
  1004. It is largely generated and follows the compiler model proposed in section 4.
  1005. Instead of generating an intermediate language,
  1006. .i Mtc
  1007. produces C code and therefore there is no need for a machine code generator.
  1008. It incorporates as much of a semantic analysis as is needed for this task.
  1009. The semantic analysis is rather complete and contains scope handling, name analysis, and type
  1010. determination. However it does not check for semantic errors, as we assume that only correct
  1011. programs will be translated.
  1012. Table 1 gives the sizes of the specifications and the generated source modules.
  1013. The design and implementation of
  1014. .i Mtc
  1015. was completed within a master thesis and took approximately 6 person months.
  1016. The program is stable and has already converted more than 100,000 lines from Modula-2 to C.
  1017. .(z
  1018. .TS
  1019. center box;
  1020. l2 |2 c2 s2 s2 |2 c2 s2 s2 |2 c1 s
  1021. l2 |2 l2 l2 l2 |2 l2 l2 l2 |2 l1 l
  1022. l2 |2 n2 n2 n2 |2 n2 n2 n2 |2 l1 l
  1023. .
  1024. part    specification    source module    tool
  1025. _
  1026.     formal    code    total    def.    impl.    total    name    references
  1027. _
  1028. scanner     392    133    525    56    1320    1376    Rex    \*([[Gro87b\*(],Gro88\*(]]
  1029. parser      951    88    1039    81    3007    3088    Ell    \*([[Gro88\*(],GrV88\*(]]
  1030. tree        189    51    240    579    2992    3571    Ast    \*([[Gro89c\*(]]
  1031. symbol table       115    938    1053    413    1475    1888    Ast    \*([[Gro89c\*(]]
  1032. semantics    1886    151    2037    9    3288    3297    Ag    \*([[Gro89d\*(]]
  1033. code generator    2793    969    3762    47    7309    7356    Estra    \*([[Vie89\*(]]
  1034. reusable parts    -    -    -    819    2722    3541    Reuse    \*([[Gro87a\*(]]
  1035. miscellaneous    -    -    -    698    3153    3851
  1036. _
  1037. total       6326    2330    8656    2702    25266    27968
  1038. .TE
  1039. .sp 0.5
  1040. .ce
  1041. Table 1: Sizes of the specifications and source modules of \fIMtc
  1042. .)z
  1043. .pp
  1044. The binary program comprises 301,240 bytes.
  1045. It runs at a speed of 810 tokens per second or 167 lines per second on a SUN
  1046. workstation (MC 68020 processor). This figures are computed by taking only
  1047. the size of the translated modules into account. If we include the definition
  1048. modules which are imported transitively and which are scanned, parsed, and
  1049. analyzed as well, we arrive at 1320 tokens per second
  1050. or 418 lines per second. In comparison, the compilers supplied by the
  1051. manufacturer run at a speed of 97 lines per second (excluding header files)
  1052. or 163 lines per second (including header files) in the case of C
  1053. and 48 lines per second in the case of Modula-2. The run time of
  1054. .i Mtc
  1055. is distributed as follows:
  1056. .(b
  1057. .TS
  1058. center;
  1059. l l.
  1060. scanning + parsing + tree construction    42 %
  1061. semantic analysis    33 %
  1062. code generation     25 %
  1063. .TE
  1064. .)b
  1065. The semantic analysis spends 95 % in attribute computations using user
  1066. supplied code and 5 % in tree traversal or visit actions respectively.
  1067. By the way, there are up to five visits to 11 node types.
  1068. .pp
  1069. .i Mtc
  1070. uses approximately 360 K Bytes dynamic memory per 1000 source lines to store
  1071. the abstract syntax tree, the attributes, and the symbol table without optimization of
  1072. attribute storage. Another 600 K Bytes are used by the transformer generated with
  1073. .i Estra .
  1074. This is bearable with today's memory capacities.
  1075. Contrary to the literature this shows that it is
  1076. possible to store all attributes in the tree. We even do this for the
  1077. environment attribute. This becomes possible by implementing the symbol
  1078. table as an abstract data type in the target language. The implementation is
  1079. time and space efficient by taking advantage of pointer semantics and
  1080. structure sharing.
  1081. .sh 2 "Code Generator for Modula-2 Compiler"
  1082. .pp
  1083. In another application we replaced the hand-written code generator of the
  1084. GMD Modula-2 compiler
  1085. .i Mocka
  1086. by two versions produced by
  1087. .i Beg .
  1088. Target machine was the MC 68020 processor. The specification of the code generator
  1089. comprises 1625 lines. It contains 187 rules and 99 intermediate language operators. To
  1090. compare the quality of the generated code, we measured the execution time for a collection of
  1091. benchmark programs (see Table 2).
  1092. .(z
  1093. .sz -2
  1094. .TS
  1095. center box tab(;);
  1096. l2 ||2 c2 |2 c2 |2 c2 |2 c2 |2 c2 |2 c2 |2 c2 |2 c2 |2 c2 |2 c2 |2 c.
  1097.  ;Perm;Towers;Queens;Intmm;Mm;Puzzle;Quick;Tree;Bubble;FFT;\(*S
  1098. _
  1099. Mocka ;40;58;37;53;103;285;32;72;56;152;888
  1100. Begra ;42;57;35;54;104;297;32;58;56;153;888
  1101. Begfly;42;57;34;54;102;299;33;56;56;151;884
  1102. Sun   ;67;90;28;83;101;263;41;81;63;150;967
  1103. .TE
  1104. .sz +2
  1105. .sp
  1106. .ce
  1107. Table 2: Comparison of code quality (run times in \fIticks\fP = 1/60 seconds)
  1108. .)z
  1109. .i Mocka
  1110. denotes the GMD Modula-2 compiler with the hand-written code generator,
  1111. .i Begra
  1112. and
  1113. .i Begfly
  1114. refer to the code generators produced by
  1115. .i Beg
  1116. with the general register allocator and the on the fly register allocator respectively, and
  1117. .i Sun
  1118. is the SUN Modula-2 compiler version 1.0. On the average code generators produced by
  1119. .i Beg
  1120. generate code that is as fast as the one from the hand-written code generator.
  1121. .\" It is 8% faster than the code produced by the SUN Modula-2 compiler.
  1122. .(z
  1123. .TS
  1124. center box tab(;);
  1125. l | n.
  1126. Mocka ;2.9
  1127. Begfly;3.2
  1128. Begra ;3.9
  1129. Sun   ;25.4
  1130. .TE
  1131. .sp
  1132. .ce
  1133. Table 3: Comparison of compilation times (times in sec.)
  1134. .)z
  1135. .pp
  1136. Table 3 compares the run times of the compilers for processing a program with 1116 lines. All
  1137. measurements were carried out on a diskless SUN 3/60, all measured times are user times. The
  1138. size of the code generator increased from 5140 lines (17,117 tokens) for the hand-written
  1139. version to 9574 lines (27,044 tokens).
  1140. .sh 1 "Summary and Future Work"
  1141. .pp
  1142. We presented a complete tool box of compiler construction tools which supports the
  1143. construction of all phases of a compiler. The tools are very powerful and flexible and
  1144. largely independent of each other. They support a wide range of compiler designs and
  1145. allow the construction of production quality compilers for many programming languages.
  1146. First realistic applications demonstrate the excellent performance of the tools.
  1147. .\" .pp
  1148. .\" We are planning to improve the existing tools and to construct some more tools.
  1149. .\" Currently a tool is being implemented which allows to describe the attribution mechanism of
  1150. .\" .i Lalr
  1151. .\" in a symbolic way and checks it for completeness and whether it fulfills the property of an
  1152. .\" S-attribution. Furthermore, the specification of the scanner is extracted largely out of the
  1153. .\" parser specification. Therefore the coding of the tokens is determined automatically and
  1154. .\" hence it is consistent in both, scanner and parser specification.
  1155. .pp
  1156. The optimization of attribute storage of
  1157. .i Ag
  1158. will be improved allowing attributes to be treated as global variables and global stacks.
  1159. The transformation of non-OAG grammars into OAG ones should be automized.
  1160. .pp
  1161. A redesign is planned for the tool
  1162. .i Estra .
  1163. The specification language will become simpler and clearer and the tool will be integrated
  1164. better with
  1165. .i Ast .
  1166. The efficiency of the generated transformation modules can be improved both in terms of run
  1167. time and storage consumption.
  1168. .pp
  1169. The optimization phase of a compiler clearly needs to be supported. This could be either done
  1170. by a reusable, language independent optimizer, by an optimizer which can be parameterized, or
  1171. by some means of an optimizer generator.
  1172. .pp
  1173. The tool
  1174. .i Beg
  1175. will be extended in the directions of the generation of a global register allocator,
  1176. support for instruction scheduling, and a facility for the direct generation of binary
  1177. object code.
  1178. .uh Acknowledgement
  1179. .pp
  1180. We thank all that have contributed to the development of this toolbox either by active
  1181. participation or with their ideas:
  1182. Michael Besser,
  1183. Carsten Gerlhof,
  1184. Bob Gray,
  1185. Rudolf Landwehr,
  1186. Matthias Martin,
  1187. Thomas M\*uller,
  1188. F. W. Schr\*oer,
  1189. Dirk Schwartz-Hertzner,
  1190. Doris Vielsack,
  1191. Bertram Vielsack und
  1192. William M. Waite.
  1193. .fi
  1194. .sz 12
  1195. .[]
  1196. .[-
  1197. .ds [F ASU86
  1198. .ds [A A\*(p]\*(a]V\*(p] Aho
  1199. .as [A \*(c]R\*(p] Sethi
  1200. .as [A \*(m]J\*(p]\*(a]D\*(p] Ullman
  1201. .ds [T Compilers: Principles, Techniques, and Tools
  1202. .ds [I Addison Wesley
  1203. .ds [C Reading, M\&A
  1204. .ds [D 1986
  1205. .][
  1206. .[-
  1207. .ds [F DeP82
  1208. .ds [A F\*(p] DeRemer
  1209. .as [A \*(n]T\*(p] Pennello
  1210. .ds [T Efficient Computation of LALR(1) Look-Ahead Sets
  1211. .nr [P 1
  1212. .ds [P 615-649
  1213. .ds [J ACM Trans. Prog. Lang. and Systems
  1214. .ds [V 4
  1215. .ds [N 4
  1216. .ds [D Oct. 1982
  1217. .][
  1218. .[-
  1219. .ds [F Emm89a
  1220. .ds [A H\*(p] Emmelmann
  1221. .ds [T Automatische Erzeugung effizienter Codegeneratoren
  1222. .ds [R GMD-Studie Nr. 158
  1223. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1224. .ds [D 1989
  1225. .][
  1226. .[-
  1227. .ds [F Emm89b
  1228. .ds [A H\*(p] Emmelmann
  1229. .ds [T BEG - A Back End Generator - User Manual
  1230. .ds [R Arbeitspapier Nr. 420
  1231. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1232. .ds [D Dec. 1989
  1233. .][
  1234. .[-
  1235. .ds [F ESL89
  1236. .ds [A H\*(p] Emmelmann
  1237. .as [A \*(c]F\*(p]\*(a]W\*(p] Schr\\*:oer
  1238. .as [A \*(m]R\*(p] Landwehr
  1239. .ds [T BEG - a Generator for Efficient Back Ends
  1240. .ds [J SI\&GPLAN Notices
  1241. .ds [V 24
  1242. .ds [N 7
  1243. .nr [P 1
  1244. .ds [P 227-237
  1245. .ds [D July 1989
  1246. .][
  1247. .[-
  1248. .ds [F Gro87a
  1249. .ds [A J\*(p] Grosch
  1250. .ds [T Reusable Software - A Collection of Modula-Modules
  1251. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1252. .ds [R Compiler Generation Report No. 4
  1253. .ds [N 4
  1254. .ds [D Sep. 1987
  1255. .][
  1256. .[-
  1257. .ds [F Gro87b
  1258. .ds [A J\*(p] Grosch
  1259. .ds [T Rex - A Scanner Generator
  1260. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1261. .ds [R Compiler Generation Report No. 5
  1262. .ds [N 5
  1263. .ds [D Dec. 1987
  1264. .][
  1265. .[-
  1266. .ds [F Gro88
  1267. .ds [A J\*(p] Grosch
  1268. .ds [T Generators for High-Speed Front-Ends
  1269. .ds [V 371
  1270. .ds [J LNCS
  1271. .ds [C Berlin
  1272. .ds [I Springer Verlag
  1273. .nr [P 1
  1274. .ds [P 81-92
  1275. .ds [D Oct. 1988
  1276. .][
  1277. .[-
  1278. .ds [F GrV88
  1279. .ds [A J\*(p] Grosch
  1280. .as [A \*(n]B\*(p] Vielsack
  1281. .ds [T The Parser Generators Lalr and Ell
  1282. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1283. .ds [R Compiler Generation Report No. 8
  1284. .ds [N 8
  1285. .ds [D Apr. 1988
  1286. .][
  1287. .[-
  1288. .ds [F Gro89a
  1289. .ds [A J\*(p] Grosch
  1290. .ds [T Efficient Generation of Lexical Analysers
  1291. .ds [J Software\(emPractice & Experience
  1292. .ds [V 19
  1293. .ds [N 11
  1294. .nr [P 1
  1295. .ds [P 1089-1103
  1296. .ds [D Nov. 1989
  1297. .][
  1298. .[-
  1299. .ds [F Gro89b
  1300. .ds [A J\*(p] Grosch
  1301. .ds [T Efficient and Comfortable Error Recovery in Recursive Descent Parsers
  1302. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1303. .ds [R Compiler Generation Report No. 19
  1304. .ds [N 19
  1305. .ds [D Dec. 1989
  1306. .][
  1307. .[-
  1308. .ds [F Gro89c
  1309. .ds [A J\*(p] Grosch
  1310. .ds [T Ast - A Generator for Abstract Syntax Trees (Revised Version)
  1311. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1312. .ds [R Compiler Generation Report No. 15
  1313. .ds [N 15
  1314. .ds [D Aug. 1989
  1315. .][
  1316. .[-
  1317. .ds [F Gro89d
  1318. .ds [A J\*(p] Grosch
  1319. .ds [T Ag - An Attribute Evaluator Generator
  1320. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1321. .ds [R Compiler Generation Report No. 16
  1322. .ds [N 16
  1323. .ds [D Aug. 1989
  1324. .][
  1325. .[-
  1326. .ds [F Gro90
  1327. .ds [A J\*(p] Grosch
  1328. .ds [T Object-Oriented Attribute Grammars
  1329. .ds [E A\*(p]\*(a]E\*(p] Harmanci
  1330. .as [E \*(n]E\*(p] Gelenbe
  1331. .nr [E 2
  1332. .ds [B Proceedings of the Fifth International Symposium on Computer and Information Sciences (ISCIS V)
  1333. .ds [C Cappadocia, Nevsehir, Turkey
  1334. .nr [P 1
  1335. .ds [P 807-816
  1336. .ds [D Oct. 1990
  1337. .][
  1338. .[-
  1339. .ds [F Gro91a
  1340. .ds [A J\*(p] Grosch
  1341. .ds [T Ast - A Generator for Abstract Syntax Trees
  1342. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1343. .ds [R Compiler Generation Report No. 15
  1344. .ds [N 15
  1345. .ds [D Sep. 1991
  1346. .][
  1347. .[-
  1348. .ds [F Gro91b
  1349. .ds [A J\*(p] Grosch
  1350. .ds [T Tool Support for Data Structures
  1351. .ds [J Structured Programming
  1352. .ds [V 12
  1353. .nr [P 1
  1354. .ds [P 31-38
  1355. .ds [D 1991
  1356. .][
  1357. .[-
  1358. .ds [F Joh75
  1359. .ds [A S\*(p]\*(a]C\*(p] Johnson
  1360. .ds [T Yacc \(em  Yet Another Compiler-Compiler
  1361. .ds [R Computer Science Technical Report 32
  1362. .ds [I Bell Telephone Laboratories
  1363. .ds [C Murray Hill, NJ
  1364. .ds [D July 1975
  1365. .][
  1366. .[-
  1367. .ds [F Kas80
  1368. .ds [A U\*(p] Kastens
  1369. .ds [T Ordered Attribute Grammars
  1370. .nr [P 1
  1371. .ds [P 229-256
  1372. .ds [J Acta Inf.
  1373. .ds [V 13
  1374. .ds [D 1980
  1375. .ds [N 3
  1376. .][
  1377. .[-
  1378. .ds [F Les75
  1379. .ds [A M\*(p]\*(a]E\*(p] Lesk
  1380. .ds [T LEX \(em A Lexical Analyzer Generator
  1381. .ds [R Computing Science Technical Report 39
  1382. .ds [I Bell Telephone Laboratories
  1383. .ds [C Murray Hill, NJ
  1384. .ds [D 1975
  1385. .][
  1386. .[-
  1387. .ds [F Mar90
  1388. .ds [A M\*(p] Martin
  1389. .ds [T Entwurf und Implementierung eines \\*:Ubersetzers von Modula-2 nach C
  1390. .ds [R Diplomarbeit
  1391. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1392. .ds [D Feb. 1990
  1393. .][
  1394. .[-
  1395. .ds [F Vie89
  1396. .ds [A B\*(p] Vielsack
  1397. .ds [T Spezifikation und Implementierung der Transformation attributierter B\\*:aume
  1398. .ds [R Diplomarbeit
  1399. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1400. .ds [D June 1989
  1401. .][
  1402. .[-
  1403. .ds [F VSK89
  1404. .ds [A H\*(p]\*(a]H\*(p] Vogt
  1405. .as [A \*(c]S\*(p]\*(a]D\*(p] Swierstra
  1406. .as [A \*(m]M\*(p]\*(a]F\*(p] Kuiper
  1407. .ds [T Higher Order Attribute Grammars
  1408. .ds [J SI\&GPLAN Notices
  1409. .ds [V 24
  1410. .ds [N 7
  1411. .nr [P 1
  1412. .ds [P 131-145
  1413. .ds [D July 1989
  1414. .][
  1415. .bp 1
  1416. .lp
  1417. .b Contents
  1418. .sp
  1419. .xp
  1420.